#include "Graph.h"
#include <stack>

//无向图中寻找「割点」和「桥」
void Tarjan_ApB(Graph* g, int start, int &times) 
{
    auto cur = g->nodeSet[start];
    cur->dfn = cur->low = ++times;
    cur->child = 0;
    for(auto n : cur->nexts)
    {
        if(n->dfn == -1)
        {
            ++cur->child;
            n->parent = cur;
            Tarjan_ApB(g, n->value, times);
            //如果当前节点是根且有不少于两个孩子
            if(cur->parent == NULL && cur->child >= 2)
                printf("%d", cur->value);//cur是割点
            //如果当前是寻常点，某子节点的low >= 当前dfn
            if(cur->parent != NULL && cur->dfn <= n->low)
                printf("%d", cur->value);//cur是割点
            //某子节点的low >= 当前dfn
            if(cur->dfn < n->low)
                //cur-->n 的边是桥
                printf("%d %d", cur->value, n->value);
            cur->low = min(cur->low, n->low);
        }
        else if(n != cur->parent)
            cur->low = min(cur->low, n->dfn);//注意这里是n->dfn
    }
}

/*
对于不完全联通的图，可遍历所有点进行Tarjan
但在Tarjan里要标记好哪些割点被记录过了，否则可能重复记录同一个割点
for (int i = 1; i <= n; ++i)
{
    int times = 0;
    if(g->nodeSet[i]->dfn == -1)
        Tarjan(g, i, times);
}
*/

//寻找强连通分量，从而完成缩点
void Tarjan_v1(Graph* g, int start, int& times, stack<GraphNode*>& st)
{
    auto cur = g->nodeSet[start];
    st.push(cur);
    cur->inSt = 1;
    cur->dfn = cur->low = ++times;
    for(auto n : cur->nexts)
    {
        if(n->dfn == -1)
        {
            Tarjan_v1(g, n->value, times, st);
            cur->low = min(cur->low, n->low);
        }
        else if(n->inSt)
            cur->low = min(cur->low, n->dfn);
    }
    if(cur->dfn == cur->low)
    {
        while (st.top() != cur)
        {
            st.top()->inSt = 0;
            st.pop();
        }
        cur->inSt = 0;
        st.pop();
    }
}

//————————实际使用——————————

int newNodeCnt;
int idTable[10005];

void Tarjan(Graph* g, int s, int& times, stack<GraphNode*>& st)
{
    auto cur = g->nodeSet[s];
    cur->dfn = cur->low = ++times;
    st.push(cur);
    cur->inSt = true;
    for(auto n : cur->nexts)
    {
        if(n->dfn == -1)
        {
            Tarjan(g, n->value, times, st);
            cur->low = min(cur->low, n->low);
        }
        else if(n->inSt)
            cur->low = min(cur->low, n->dfn);
    }
    if(cur->low == cur->dfn)
    {
        while(st.top() != cur)
        {
            cur->weight += st.top()->weight;//将环中节点的权重加到统一节点
            st.top()->value = cur->value;//修改环中的节点归属
            st.top()->inSt = false;
            st.pop();
        }
        st.top()->inSt = false;
        st.pop();
        //将缩点后的节点编号与旧图的节点编号对应
        idTable[cur->value] = newNodeCnt++;
    }
}

//构建缩点后的新图
Graph* BuildNewGraph(Graph* g, int oldNodeCnt, int newNodeCnt)
{
    Graph *ng = new Graph(newNodeCnt);
    for (int i = 1; i <= oldNodeCnt; ++i)
    {
        auto n = g->nodeSet[i];
        int f = idTable[n->value];
        if(n->value != i)
        {
            ng->nodeSet[f]->weight = n->weight;
        }
        for (auto e : n->edges)
        {
            if (e->from->value != e->to->value)
            {
                int t = idTable[e->to->value];
                ng->AddPath(f, t, e->weight);
            }
        } 
    }
    return ng;
}

